/*
 * @lc app=leetcode.cn id=222 lang=javascript
 *
 * [222] 完全二叉树的节点个数
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * 二分法, 对每个节点做左右子树的高度判断, 
 * 相等 左子树肯定的是满二叉树 接着对右子树做递归调用
 * 不等 说明右子树是满二叉树 左子树有可能不是满二叉树 需要对左子树递归
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    const height = function(node) {
        let h = 0
        while (node) {
            h++
            node = node.left
        }
        return h
    }
    const dfs = function(node) {
        if (!node) return 0
        let l = height(node.left)
        let r = height(node.right)
        if (l === r) {
            return dfs(node.right) + (1<<l)
        } else {
            return dfs(node.left) + (1<<r)
        }
    }
    return dfs(root)
};
// @lc code=end

// const { buildBinaryTree } = require('./tools')
// const root = buildBinaryTree([1,2,3,4,5,6,7,8,9,10])

// countNodes(root)